This invention relates to a scan-conversion process for converting a graphic primitive described by its outline to a pixel map suitable for raster output, and to a processor for executing this scan-conversion process.
Scan conversion is widely practiced in fields such as desktop publishing, computer-aided design, and computer graphics. In the desktop publishing field, for example, page description languages such as the well-known PostScript language enable graphic primitives such as characters and arbitrary graphic figures to be expressed in terms of their outlines. When such graphic primitives are printed or displayed on a raster output device such as a dot-matrix or laser printer or cathode-ray tube (CRT) display, the outlines must be filled in with pixels disposed on the scan lines of the output device. This filling-in process is the scan-conversion process.
In the past, the scan-conversion process has usually been executed by a general-purpose microprocessor, but it requires extensive computation, which can take considerable time. Software techniques have accordingly been developed to shorten the time, as described, for example, on pp. 456-460 of Fundamentals of Interactive Computer Graphics by J. D. Foley and A. Van Dam, published by the Addison Wesley Publishing Company in 1984.
The scan-conversion process described in this reference employs a bucket-sorted edge table having one "bucket" for each scan line. Information about the outline of a graphic primitive is stored in this table, information for each edge being stored in the bucket of the minimum y-coordinate of the edge. The scan-conversion process is executed one scan line at a time. An active edge table, indicating the edges that intersect the current scan line, is created and updated using the information in the bucket-sorted edge table.
A problem of this prior-art scan-conversion process is that it becomes inefficient in its use of memory when the number of scan lines is very large. Some raster output devices have a resolution of approximately 10,000.times.10,000 dots per page. If the scan-conversion process described above were to be applied, it would employ an edge table having 10,000 buckets, even for graphic primitives with a much smaller number of edges.
The scan-conversion process could be significantly speeded up by execution on a dedicated processor, instead of a general-purpose microprocessor. Ideally, the dedicated processor should be implemented as a single integrated circuit on a semiconductor chip. The amount of memory space needed to store the edge table in the prior-art scan conversion process, however, tends to preclude such a dedicated processor on a single chip, even if very-large-scale integration (VLSI) is employed. The edge table must therefore be stored in an external memory, but this complicates the design of the processing system. Extra time is also required to transfer edge information between the dedicated processor and external memory, thus delaying the scan-conversion process.
Another problem with the prior-art scan-conversion process is that it restricts the algorithm used to discriminate between the interior and exterior of a graphic primitive, hence imposes restrictions on the way in which a graphic primitive can be defined. The prior-art scan-conversion process employs a type of even-odd algorithm, in which every edge is assumed to be a boundary between the interior and exterior. This prevents the correct scan conversion of graphic primitives with a self-intersecting outline that may wind around an interior region twice.
The PostScript language, for example, enables two algorithms to be selected for interior-exterior discrimination: the even-odd algorithm, and the non-zero-winding algorithm. The non-zero-winding algorithm allows an outline to wind around an interior region any number of times, providing additonal flexibility in the definition of graphic primitives. The prior-art scan-conversion process described above does not support the non-zero-winding algorithm, hence it fails to support the full range of features provided by the widely-used PostScript language, and needed in many computer graphics applications.